﻿#include <iostream>
#include <string>
using namespace std;

class Solution {
public:
    string minWindow(string s, string t) {
        int hash1[128] = { 0 };
        int hash2[128] = { 0 };
        int kinds = 0;
        for (auto e : t) if (hash1[e]++ == 0) kinds++;
        int start = -1;
        int len = INT_MAX;
        //count 统计有效字符的种类(不是个数)
        for (int left = 0, right = 0, count = 0; right < s.size(); right++)
        {
            char in = s[right];
            if (++hash2[in] == hash1[in]) count++;
            //count == t.size() 时候符合要求 --right不动 
            while (count == kinds)
            {
                //更新
                if (right - left + 1 < len)
                {
                    len = right - left + 1;
                    start = left;
                }
                char out = s[left++];
                if (hash2[out]-- == hash1[out]) count--;
            }
        }
        if (start == -1)
        {
            return "";
        }
        else
        {
            return s.substr(start, len);
        }
    }
};

